//构建乘积数组
class Solution {
public:
    vector<int> constructArr(vector<int>& a) 
    {
        //结果集中任何一个元素 = 其左边所有元素的乘积 * 其右边所有元素的乘积。
        //一轮循环构建左边的乘积并保存在结果集中，二轮循环 构建右边乘积的过程，
        //乘以左边的乘积，并将最终结果保存
        vector<int>res(a.size(),1);
        //left[i]表示不包括下标i的 左边元素的乘积
        vector<int>left(a.size(),1);
        //right[i]表示不包括下标i的 右边元素的乘积
        vector<int>right(a.size(),1);
        //1  2  3  4  5
        //1  1  2  6  24
        for(int i=1;i<a.size();i++)
        {
            left[i]=left[i-1]*a[i-1];
        }
        for(int j=a.size()-1-1;j>=0;j--)
        {
            right[j]=right[j+1]*a[j+1];
        }
        for(int i=0;i<a.size();i++)
        {
            res[i]=left[i]*right[i];
        }
        return res;
    }
};
//最长重复子数组
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) 
    {
        //dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B
        //最长重复子数组长度为dp[i][j]
        int res=0;
        int m=nums1.size()+1;
        int n=nums2.size()+1;
        vector<vector<int>>dp(m,vector<int>(n,0));
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(nums1[i-1]==nums2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    res=res>dp[i][j]?res:dp[i][j];
                }
            }
        } 
        return res;
    }
};
